# 搜索二维矩阵： https://leetcode-cn.com/problems/search-a-2d-matrix/submissions/

# 只是用一遍二分查找
class Solution:
    def searchMatrix(self, matrix: list, target: int) -> bool:
        """
            二分查找，每一行都是有顺序的，那么整体二维数组也可以看成是有序的一维数组
        """
        left, right = 0, len(matrix) *len(matrix[0]) - 1
        col = len(matrix[0])
        while left <= right:
            mid = left + (right - left) // 2
            if matrix[mid // col][mid % col] == target:
                return True
            elif matrix[mid // col][mid % col] > target:
                right = mid - 1
            else:
                left = mid + 1
        
        return False
        